package com.atguigu.linkedlist;

/**
 * @author Amos
 * @date 2022/6/5
 */

public class MergeLinkedList {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        System.out.println("打印list1");
        list(node1);

        ListNode node4 = new ListNode(1);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(4);
        node4.next = node5;
        node5.next = node6;
        System.out.println("打印list2");
        list(node4);

        ListNode list1 = node1;
        ListNode list2 = node4;

        ListNode mergeTwoLists = mergeTwoLists(list1, list2);
        // 打印合并后的链表
        System.out.println("打印合并后的链表");
        list(mergeTwoLists);
    }

    private static void list(ListNode node) {
        while (node != null) {
            System.out.println(node);
            node = node.next;
        }
    }

    private static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode mergeList = new ListNode(0);
        ListNode temp = mergeList;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        if (list1 == null) temp.next = list2;
        if (list2 == null) temp.next = list1;

        return mergeList.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}
